package leetcode.Hot100;

/**
 * @author Cheng Jun
 * Description: 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
 * <p>
 * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
 * <p>
 * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2021/11/26 22:48
 * 难度级别：困难
 * 二刷，面试题
 * 最多只能进行两次交易
 */
public class maxProfit3 {

    public static void main(String[] args) {
        System.out.println(maxProfit(new int[]{2, 1, 2, 0, 1}));
    }

    // 交易状态分析：任何一天结束都只有五种情况
    // 1. 没有交易
    // 2. 第一次买进
    // 3. 第一次卖出
    // 4. 第二次买进
    // 5. 第二次卖出
    // 第一种情况 没有必要分析，没有交易的话，收益永远为 0
    // 注意分析下面四种情况的动态转移方程
    // 隐含条件：无论题目中是否 允许同一天买入和卖出的操作，对结果都没影响。因为同一天买入并且卖出，收益为0。
    // 只有读懂了隐含条件才能 理解 dp数组的初始化
    static int maxProfit(int[] prices) {
        int buy1 = -prices[0];
        int sell1 = 0;
        int buy2 = -prices[0];
        int sell2 = 0;
        for (int i = 1; i < prices.length; i++) {
            int tempBuy1 = Math.max(buy1, -prices[i]);
            int tempSell1 = Math.max(sell1, buy1 + prices[i]);
            int tempBuy2 = Math.max(buy2, sell1 - prices[i]);
            int tempSell2 = Math.max(sell2, buy2 + prices[i]);
            buy1 = tempBuy1;
            sell1 = tempSell1;
            buy2 = tempBuy2;
            sell2 = tempSell2;
        }
        return Math.max(sell1, sell2);
    }
}
